#include<iostream>
using namespace std;


namespace bite
{
    // List的节点类
    template<class T>
    struct ListNode
    {
        ListNode(const T& val = T()):_val(val), _pPre(nullptr), _pNext(nullptr) {} //构造函数
        ListNode<T>* _pPre;
        ListNode<T>* _pNext;
        T _val;
    };


    //List的迭代器类
    template<class T, class Ref, class Ptr>
    struct ListIterator
    {
        typedef ListNode<T>* PNode;
        typedef ListIterator<T, Ref, Ptr> Self;

        
        ListIterator(PNode pNode = nullptr)
        {
            _pNode = pNode;
        }
        //拷贝构造函数
        ListIterator(const Self& l)
        {
            _pNode = l._pNode;

        }

        T& operator*()
        {
            return _pNode->_val;
        }

        T* operator->()
        {
            return &(_pNode->_val);
        }
        
        Self& operator++()
        {
            _pNode = _pNode->_pNext;
            return *this;
        }

        Self operator++(int)
        {
            Self tmp = *this;
            _pNode = _pNode->_pNext;
            return tmp;
        }

        Self& operator--()
        {
            _pNode = _pNode->_pPre;
            return *this;
        }
        Self& operator--(int)
        {
            Self tmp = *this;
            _pNode = _pNode->_pPre;
            return tmp;
        }
        bool operator!=(const Self& l)
        {
            return _pNode != l._pNode;
        }
        bool operator==(const Self& l)
        {
            return _pNode == l._pNode;
        }
        
        
        PNode _pNode=nullptr;
    };


    //list类
    template<class T>
    class list
    {
        typedef ListNode<T> Node;
        typedef Node* PNode;
    public:
        
        typedef ListIterator<T, T&, T*> iterator;
        typedef ListIterator<T, const T&, const T*> const_iterator;

    public:
        ///////////////////////////////////////////////////////////////
        // List的构造
        list()
        {
            CreateHead();
        }

        list(int n, const T& value = T())
        {
            CreateHead();
            for (int i = 0; i < n; ++i)
            {
                PNode newNode = new Node(value);
                newNode->_pPre = _pHead->_pPre;
                newNode->_pNext = _pHead;
                _pHead->_pPre->_pNext = newNode;
                _pHead->_pPre = newNode;
            }
        }

        template <class Iterator>
        list(Iterator first, Iterator last)
        {
            CreateHead();
            while (first != last)
            {
                PNode newNode = new Node(*first);
                newNode->_pPre = _pHead->_pPre;
                newNode->_pNext = _pHead;
                _pHead->_pPre->_pNext = newNode;
                _pHead->_pPre = newNode;
                ++first;
            }
        }

        list(const list<T>& l)
        {
            CreateHead();
            for (auto it = l.begin(); it != l.end(); ++it)
            {
                PNode newNode = new Node(*it);
                newNode->_pPre = _pHead->_pPre;
                newNode->_pNext = _pHead;
                _pHead->_pPre->_pNext = newNode;
                _pHead->_pPre = newNode;
            }
        }

        list<T>& operator=(const list<T> l)
        {
            if(this ==&l) return *this; //自赋值检查
            else
            {
                list<T> tmp(l); //拷贝构造函数
                swap(tmp); //交换
                return *this; //返回当前对象的引用
            }
        }
        ~list()
        {
            PNode pCur=_pHead->_pNext;
            while(pCur!=_pHead)
            {
                PNode pNext=pCur->_pNext;
                delete pCur; //释放节点
                pCur=pNext; //指向下一个节点
            }
            delete _pHead; //释放头节点
            _pHead=nullptr; //置空
        }


        ///////////////////////////////////////////////////////////////
        // List Iterator
        iterator begin()
        {
            return iterator(_pHead->_pNext); //返回第一个节点的迭代器
        }
        iterator end()
        {
            return iterator(_pHead); //返回头节点的迭代器
        }
        const_iterator begin() const
        {
            return const_iterator(_pHead->_pNext); //返回第一个节点的迭代器
        }
        const_iterator end() const
        {
            return const_iterator(_pHead); //返回头节点的迭代器
        }


        ///////////////////////////////////////////////////////////////
        // List Capacity
        size_t size()const
        {
            size_t count = 0;
            PNode pCur = _pHead->_pNext;
            while (pCur != _pHead)
            {
                ++count;
                pCur = pCur->_pNext;
            }
            return count; //返回节点个数

        }

        bool empty()const
        {
            return _pHead->_pNext == _pHead; //判断是否为空
        }


        ////////////////////////////////////////////////////////////
        // List Access
        T& front()
        {
            return _pHead->_pNext->_val; //返回第一个节点的值
        }

        const T& front()const
        {
            return _pHead->_pNext->_val; //返回第一个节点的值
        }

        T& back()
        {
            return _pHead->_pPre->_val; //返回最后一个节点的值
        }
        const T& back()const
        {
            return _pHead->_pPre->_val; //返回最后一个节点的值
        }


        ////////////////////////////////////////////////////////////
        // List Modify
        void push_back(const T& val) { insert(end(), val); }
        void pop_back() { erase(--end()); }
        void push_front(const T& val) { insert(begin(), val); }
        void pop_front() { erase(begin()); }
        // 在pos位置前插入值为val的节点
        iterator insert(iterator pos, const T& val)
        {
            if (pos._pNode == nullptr) return nullptr; //检查位置是否合法
            PNode newNode = new Node(val); //创建新节点
            newNode->_pPre = pos._pNode->_pPre; //前驱指针指向pos的前驱节点
            newNode->_pNext = pos._pNode; //后继指针指向pos节点
            pos._pNode->_pPre->_pNext = newNode; //前驱节点的后继指针指向新节点
            pos._pNode->_pPre = newNode; //pos节点的前驱指针指向新节点
            return iterator(newNode); //返回新节点的迭代器
        }
        // 删除pos位置的节点，返回该节点的下一个位置
        iterator erase(iterator pos)
        {
            if(pos._pNode == nullptr) return nullptr; //检查位置是否合法
            PNode pCur = pos._pNode; //保存当前节点
            PNode pNext = pCur->_pNext; //保存下一个节点
            pCur->_pPre->_pNext = pNext; //前驱节点的后继指针指向下一个节点
            pNext->_pPre = pCur->_pPre; //下一个节点的前驱指针指向当前节点的前驱节点
            delete pCur; //删除当前节点
            return iterator(pNext); //返回下一个节点的迭代器
        }

        void clear()
        {
            PNode pCur=_pHead->_pNext; //指向第一个节点
            while(pCur!=_pHead) //遍历所有节点
            {
                PNode pNext=pCur->_pNext; //保存下一个节点
                delete pCur; //删除当前节点
                pCur=pNext; //指向下一个节点
            }
            _pHead->_pNext = _pHead; //头节点的后继指针指向头节点
            _pHead->_pPre = _pHead; //头节点的前驱指针指向头节点


        }
        void swap(list<T>& l)
        {
            std::swap(_pHead, l._pHead); //交换头节点

        }
    private:
        void CreateHead()
        {
            _pHead = new Node;
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
        }
        PNode _pHead;
    };
};